class Graph
  def initialize(nodes=[])
    @nodes=nodes;
  end

  def dfs(id)
    open_all
    node = get_node(id)
    node.dfs
    print "\n"
  end

  def bfs(id)
    open_all
    que = []
    start_node = get_node(id)
    que.push(start_node)

    while !que.empty? do
      n = que.first
      print n.id
      print " "
      que.delete(n);
      n.flag = :closed
      opened_neighbors = n.neighbors.select { |x| x.flag == :opened }
      if opened_neighbors != nil
        opened_neighbors.each { |x| que.push(x) }
      end
    end
    print "\n"
  end

  def get_node(id)
    n = @nodes.select {|x| x.id==id}
    if n == nil
      return nil;
    else
      return n[0]
    end
  end

  def add_node(id)
    n=nil
    if get_node(id)==nil
      n = Node.new(id)
      @nodes << n
      return n
    else
      return get_node(id)
    end

  end

  def open_all
    @nodes.each { |x| x.flag = :opened }
  end

  def to_s
    out = "Graph: #{@nodes.length}\n"
    out += @nodes.to_s
    out
  end

end